package org.example.l0;

import org.example.leetcpde.IListNode;

import java.util.Deque;
import java.util.LinkedList;

public class list
        implements IListNode {

    public int[] maxSlidingWindow(int[] nums,
                                  int k) {
        int len = nums.length;
        int[] res = new int[len - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        res[0] = nums[deque.peekFirst()];

        for (int i = k; i < len; i++) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }

            res[i - k + 1] = nums[deque.peekFirst()];
        }

        return res;
    }

    public ListNode reverseList(ListNode head) {
        ListNode newHead = new ListNode();
        while (head != null) {
            ListNode next = head.next;
            head.next = newHead.next;
            newHead.next = head;
            head = next;
        }

        return newHead.next;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pa = headA, pb = headB;
        while (pa != pb) {
            pa = pa == null ? headB : pa.next;
            pb = pb == null ? headA : pb.next;
        }

        return pa;
    }

    public void moveZeroes(int[] nums) {
        for (int i = 0, p0 = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                swap(nums, i, p0);
                p0++;
            }
        }
    }

    void swap(int[] nums,
              int i,
              int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}